package train48days;

import java.util.Scanner;

public class 斐波那契凤尾 {
    public static void main(String[] args) {
        int index = -1;
        long[] arr = new long[100000];
          arr[0] = 1;
          arr[1] = 2;
        for (int i = 2; i < 100000; i++) {
            long next = arr[i-1]+arr[i-2];
            if (index==-1&& next>=100000){
                index=i+1;
            }
            arr[i] = next%1000000;
        }
        Scanner sc = new Scanner(System.in);
        while (sc.hasNext()){
            int n = sc.nextInt();
            long a=arr[n-1];
            if (n<index){
                System.out.printf("d\n",a);
            }else {
                System.out.printf("06d\n",a);
            }
        }
    }
}
